package sort;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author 美女
 * @date 2022/04/09 17:03
 **/
public class SevenSort {
    /**
     * 1.冒泡排序
     * 每趟排完序最大元素就位于了最后位置
     */
    public static void bubbleSort(int[] arr){
        //外层循环是比较的趟数
        //内层循环进行元素的比较交换，注意防止越界
        //可以设置标记为发现是否有交换，如果内部循环没有一次交换说明数组已经有序，无需再比较
        for (int i = 0; i < arr.length - 1; i++) {
            Boolean isSwaped=false;
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    isSwaped=true;
                }
            }
            if(!isSwaped){
                break;
            }
        }
    }

    /**
     * 2.堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        //1.heapify：先堆化让变为最大堆
        //从最后一个叶子节点开始siftdown
        for (int i = (arr.length - 1) / 2; i >= 0 ; i--) {
            siftDown(arr,i,arr.length);
        }
        //走到这里已经是最大堆了。再次遍历，交换堆顶元素与最后一个元素，再循环对除最后一个元素以外的作为一个堆进行下沉操作
        for (int i = arr.length-1; i >=0 ; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    private static void siftDown(int[] arr, int i, int length) {
        //对i进行下沉操作
        //当有左右孩子才能下沉，下沉到当前值大于左右孩子值下沉结束
        while (2*i+1<length){
            //判断是否有右孩子
            int j=(i<<1)+1;
            if(j+1<length&&arr[j]<arr[j+1]){
                j=j+1;
            }
            //此时j是左右孩子的较大值的索引
            if(arr[i]>arr[j]){
                break;
            }else{
                swap(arr,i,j);
                i=j;
            }
        }
    }

    /**
     * 3.选择排序-不稳定排序
     */
    //3.1单向选择排序
    public static void selectionSort(int[] arr){
        //最开始无序区间[0...n]，有序区间[]
        //arr.length-1:当无需区间只剩一个元素时，整个集合已经有序，所以可以少走一次（-1）
        //从无需区间找最小值，存放在最前面位置
        for (int i = 0; i < arr.length-1; i++) {//区间只剩一个元素，集合有序，少走一次
            int min=i;//默认最小值
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            swap(arr,i,min);
        }
    }
    //3.2双向选择排序
    //注意max在low处时，最小值放在low处会把max对应的最大值换走，这块需要max=min更新一下索引指向
    public static void selectionSort2(int[] arr){
        int low=0;
        int high= arr.length-1;
        while (low<=high){
            int min=low;
            int max=low;
            for (int i = low+1; i <=high ; i++) {
                if(arr[i]<arr[min]){
                    min=i;
                }
                if(arr[i]>arr[max]){
                    max=i;
                }
            }
            swap(arr,min,low);
            if(max==low){
                max=min;
            }
            swap(arr,max,high);
            low++;
            high--;
        }
    }

    /**
     * 4.插入排序
     * @param arr
     */
    //4.1直接插入
    public static void insertionSort(int[] arr){
        /**
         * 1.
         */
//        for (int i = 1; i < arr.length; i++) {
//            for (int j = i; j > 0 ; j--) {
//                if(arr[j]>=arr[j-1]){
//                    break;
//                }else{
//                    swap(arr,j,j-1);
//                }
//            }
//        }
        /**
         * 2.
         */
//        for (int i = 1; i < arr.length; i++) {
//            for (int j = i; j>0&&arr[j]<arr[j-1] ; j--) {
//                swap(arr,j,j-1);
//            }
//        }
        /**
         * 3.不用swap，直接覆盖
         */
//        for (int i = 1; i < arr.length; i++) {
//            int j = i;
//            int val=arr[j];
//            for (; j > 0 ; j--) {
//                if(val>=arr[j-1]){
//                    arr[j]=val;
//                    break;
//                }else{
//                    arr[j]=arr[j-1];
//                }
//            }
//            arr[j]=val;
//        }
        /**
         * 4.
         */
        for (int i = 1; i < arr.length; i++) {
            int j=i;
            int val=arr[j];
            for (; j > 0 && val<arr[j-1] ; j--) {
                arr[j]=arr[j-1];
            }
            arr[j]=val;
        }
        //1.2.3.4.等价
    }
    //4.2折半插入
    public static void insertionSortBS(int[] arr){
        //有序区间[0,i)
        //无序区间[i,n)
        for (int i = 1; i < arr.length ; i++) {
            int left=0;
            int right=i;//i索引取不到
            int val=arr[i];
            while(left<right){
                //开始折半查找
                int mid=((right-left)>>1)+left;
                if(val<arr[mid]){
                    right=mid;
                }
                if(val>arr[mid]){
                    left=mid+1;
                }
            }
            //搬移left...i元素
            for (int j = i; j > left ; j--) {
                arr[j]=arr[j-1];
            }
            //left就是待插入位置
            arr[left]=val;
        }
    }

    /**
     * 5.希尔排序
     * 待排序数组按gap分组，不同组之间按gap分组进行插入排序，排序后gap/=2or3
     * 直到gap=1,再在整个数组上进行插排（插排在近乎有序的区间效率非常之高）
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap= arr.length>>1;
        while(gap>1){
            insertionSortByGap(arr,gap);
            gap/=2;
        }
        insertionSort(arr);
    }

    /**
     * 按gap分组进行插入排序
     * @param arr
     * @param gap
     */
    private static void insertionSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j-gap >=0&&arr[j]<arr[j-gap] ; j-=gap) {
                swap(arr,j,j-gap);
            }
        }
    }

    /**
     * 6.归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortInteral(arr,0,arr.length-1);
    }

    /**
     * 在arr[left,right]上进行归并排序
     * @param arr
     * @param left
     * @param right
     */
    private static void mergeSortInteral(int[] arr, int left, int right) {
        //归-先将数组逐步拆分
//        if(left>=right){
//            return;
//        }
        //小区间插入排序效果才最好
        if(right-left<=15){
            insertionSort(arr,left,right);
            return;
        }
        //将原数组拆分成两个小区间，分别进行归并排序
        int mid=((right-left)>>1)+left;
        mergeSortInteral(arr,left,mid);
        mergeSortInteral(arr,mid+1,right);
        //拆分完毕，合并
        if(arr[mid]>arr[mid+1]){
            merge(arr,left,mid,right);
        }
    }
    //归并排序上使用插入排序
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left+1; i <=right; i++) {
            for (int j = i; j >left&&arr[j]<arr[j-1] ; j--) {
                swap(arr,j,j-1);
            }
        }
    }


    /**
     * merge操作合并数组
     * 创建临时数组aux，避免覆盖
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] aux=new int[right-left+1];
        for (int i = 0; i < aux.length; i++) {
            aux[i]=arr[i+left];
        }
        int i=left;
        int j=mid+1;
        for (int k = left; k <= right; k++) {
            if(i>mid){
                arr[k]=aux[j-left];
                j++;
            }else if(j>right){
                arr[k]=aux[i-left];
                i++;
            }else if(aux[i-left]<=aux[j-left]){
                arr[k]=aux[i-left];
                i++;
            }else{
                arr[k]=aux[j-left];
                j++;
            }
        }
    }

    /**
     * 7.快速排序
     * @param arr
     */
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length-1);
    }
    //对l...r区间内的元素进行快速排序
    private static void quickSortInternal(int[] arr, int l, int r) {
//        if(l>=r){//只有一个元素时已经有序，返回即可
//            return;
//        }
        if(r-l<=15){
            insertionSort(arr,l,r);
            return;
        }
        //分区点
        int p=partition(arr,l,r);
        //递归在分区点左右区间继续分区
        quickSortInternal(arr,l,p-1);
        quickSortInternal(arr,p+1,r);
    }
    private static final ThreadLocalRandom random=ThreadLocalRandom.current();
    //快排的核心操作-分区
    private static int partition(int[] arr, int l, int r) {
        int randomIndex=random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v=arr[l];//选取到基准值
        //i:当前遍历元素的下标；j:小于基准值的最后一个元素的下标
        //arr[l+1...j]<v
        //arr[j+1...i)>=v
        //最开始时上面两个区间没有元素，是空区间，赋值时注意
        int j=l;
        for (int i = l+1; i <= r; i++) {
            if(arr[i]<v){
                swap(arr,i,j+1);
                j++;
            }
        }
        //走完循环，交换j与l对应元素，基准值放到最终位置
        swap(arr,l,j);
        return j;//返回基准值对应索引
    }

    /**
     * 7.2快排的非递归写法
     * 借助栈和队列实现非递归的分治快排
     * @param arr
     */
    public static void quickSortNonRecursion(int[] arr){
        //栈中保存当前集合的开始和终止位置；注意：栈是先入后出的
        Deque<Integer> stack=new ArrayDeque<>();
        int l=0;
        int r=arr.length-1;
        //将当前集合开始位置与借书位置入栈
        stack.push(r);
        stack.push(l);
        while(!stack.isEmpty()){
            int left=stack.pop();
            int right=stack.pop();
            //栈不为空时持续执行
            if(left>=right){
                //数组只剩一个元素了，无需再分
                continue;
            }
            //获取分区点
            int p=partitionAgainst(arr,left,right);
            //将分区点左右数组各自的首尾位置入栈
            stack.push(right);
            stack.push(p+1);
            stack.push(p-1);
            stack.push(left);
        }
    }

    /**
     * 在arr[left...right]上获取分区点，返回分区点的索引
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partitionAgainst(int[] arr, int left, int right) {
        //和partition一模一样，再写一遍加强记忆
        //随机选数作为基准
        int randomIndex= random.nextInt(left,right);
        swap(arr,randomIndex,left);
        int v=arr[left];
        //开始遍历
        //arr[l+1...j]<v
        //arr[j+1...i)>v
        //i是正在遍历的元素下标
        int j=left;
        for (int i = j+1; i <= right ; i++) {
            //小于基准值时，将当前位置的值与大于基准值的第一个元素（索引：j+1）做交换,同时i,j都要后移
            if(arr[i]<v){
                swap(arr,i,j+1);
                j++;
            }
        }
        //走到这里数组遍历完毕。j在小于基准值的最后一个元素
        swap(arr,left,j);
        return j;
    }

    /**
     * 7.3二路快排
     * 将相等的元素均分到左右两个子区间
     * 使用两个变量i和j，i从前向后扫描，碰到第一个arr[i]>=v的元素停止
     * j从后向前扫描，碰到第一个<=v的元素停止，把这两个元素交换(swap(arr,i,j))
     * 这样就可以把相等元素平均到左右两个子区间，j会落在最后一个<=v的元素上
     * @param arr
     */
    public static void quickSort2(int[] arr){
        quickSortInternal2(arr,0,arr.length-1);
    }

    private static void quickSortInternal2(int[] arr, int l, int r) {
        if(r-l<=15){
            insertionSort(arr,l,r);
            return;
        }
        int p=partition2(arr,l,r);
        quickSortInternal2(arr,l,p-1);
        quickSortInternal2(arr,p+1,r);
    }

    /**
     * 二路快排的分区
     * 将相等元素均分在左右
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition2(int[] arr, int l, int r) {
        int randomIndex=random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v=arr[l];
        //i是从左往右正在遍历的元素下标，j是从右往左正在遍历的元素下标
        //arr[l+1...i)<=v
        //arr(j...r]>=v
        int i=l+1;
        int j=r;
        while(true){
            //i网友走，j往左走
            while(i<=j&&arr[i]<v){
                i++;
            }
            while(j>=i&&arr[j]>v){
                j--;
            }
            //走到i>=j就走完了，此时j索引对应元素是<v的最后一个元素
            if(i>=j){
                break;
            }
            //走到这里i走到了>=v的元素，j走到了<=v的元素，交换
            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
